﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._20
{
    public class Leetcode18
    {
        public void Test()
        {
            try
            {
                FourSum(new int[] { 1, -2, -5, -4, -3, 3, 3, 5 }, -11);
            }
            catch (Exception ex)
            { }
        }

        /*
         18. 4Sum

            Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

             */
        public IList<IList<int>> FourSum(int[] nums, int target)
        {
            List<List<int>> listListInt = new List<List<int>>();
            Array.Sort(nums);
            int tempInt = 0, tempA = 0, tempB = 0, tempC = 0, tempD = 0;
            bool lastHasOutput = false;
            for (int a = 0; a < nums.Length - 3; a++)
            {
                tempA = nums[a];
                tempInt = tempA;
                if (tempInt > 0 && tempInt > target)
                    break;
                if (lastHasOutput && a > 0 && nums[a] == nums[a - 1])
                    continue;
                lastHasOutput = false;
                for (int b = a + 1; b < nums.Length - 2; b++)
                {
                    tempB = nums[b];
                    tempInt = tempA + tempB;
                    if (tempInt > 0 && tempInt > target)
                        break;
                    if (b > a + 1 && tempB == nums[b - 1])
                        continue;

                    for (int c = b + 1; c < nums.Length - 1; c++)
                    {
                        tempC = nums[c];
                        tempInt = tempA + tempB + tempC;
                        if (tempInt > 0 && tempInt > target)
                            break;
                        if (c > b + 1 && tempC == nums[c - 1])
                            continue;
                        for (int d = c + 1; d < nums.Length; d++)
                        {
                            tempD = nums[d];
                            if (tempInt + tempD == target)
                            {
                                List<int> listTemp = new List<int>();
                                listTemp.Add(tempA);
                                listTemp.Add(tempB);
                                listTemp.Add(tempC);
                                listTemp.Add(tempD);
                                lastHasOutput = true;
                                listListInt.Add(listTemp);
                                break;
                            }
                        }
                    }

                }
            }
            return listListInt.ToArray();
        }
    }
}
